﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Fractalz.Utilities 
{
	/// <summary>
	/// Reorderable Random-Access Queue.
	/// </summary>
	/// <typeparam name="T"></typeparam>
	class PriorityQueue<T> : Queue<T>, IEnumerable<T>, ICollection<T>
	{
		private List<T> itemArray;
		
		/// <summary>
		/// Initializes a new empty PriorityQueue with the default capacity.
		/// </summary>
		public PriorityQueue()
		{
			itemArray = new List<T>();
		}

		/// <summary>
		/// Initializes a new PriorityQueue with the same items as a specified collection.
		/// </summary>
		/// <param name="col">collection to import</param>
		public PriorityQueue(ICollection<T> col)
		{
			IEnumerator<T> ienum = col.GetEnumerator();
			itemArray = new List<T>();
			while (ienum.MoveNext())
			{
				itemArray.Add(ienum.Current);
			}
		}

		/// <summary>
		/// Initializes a new empty PriorityQueue with a given capacity.
		/// </summary>
		/// <param name="capacity">Initial Capacity</param>
		public PriorityQueue(int capacity)
		{
			itemArray = new List<T>(capacity);
		}

		/// <summary>
		/// Removes all objects from the PriorityQueue.
		/// </summary>
		public new void Clear()
		{
			itemArray.Clear();
		}

		/// <summary>
		/// Determines whether an element is in the PriorityQueue.
		/// </summary>
		/// <param name="item">The item to locate in the
		/// PriorityQueue.  The value can be null.</param>
		/// <returns>true if obj is found in the
		/// PriorityQueue; otherwise, false.</returns>
		public new bool Contains(T item)
		{
			return itemArray.Contains(item);
		}

		/// <summary>
		/// Removes and returns the object at the beginning of the PriorityQueue.
		/// </summary>
		/// <returns>The object that is removed from the beginning of the PriorityQueue.</returns>
		/// <exception cref="System.InvalidOperationException">The PriorityQueue is empty.</exception>
		public new T Dequeue()
		{
			if (itemArray.Count == 0)
			{
				throw new InvalidOperationException("The PriorityQueue is Empty");
			}
			T temp = itemArray.First();
			itemArray.RemoveAt(0);
			return temp;
		}

		/// <summary>
		/// Adds an item to the end of the PriorityQueue.
		/// </summary>
		/// <param name="item">The object to add to the PriorityQueue.  The value can be null.</param>
		public new void Enqueue(T item)
		{
			itemArray.Add(item);
		}

		/// <summary>
		/// Returns the object at the beginning of the PriorityQueue without removing it.
		/// </summary>
		/// <returns>The object at the beginning of the PriorityQueue.</returns>
		/// <exception cref="InvalidOperationException">The PriorityQueue is empty.</exception>
		public new T Peek()
		{
			try
			{
				return itemArray.First();
			}
			catch (InvalidOperationException e)
			{
				throw e;
			}
		}

		/// <summary>
		/// Copies the PriorityQueue elements to a new array.
		/// </summary>
		/// <returns>A new array containing elements copied from the PriorityQueue.</returns>
		public new T[] ToArray()
		{
			return itemArray.ToArray();
		}

		/// <summary>
		/// Returns the element at a specified index in the PriorityQueue.
		/// </summary>
		/// <param name="index"></param>
		/// <returns></returns>
		/// <example>This sample retrieves the element at the front of the PriorityQueue.
		/// <code>ElementAt(0);</code>
		/// </example>
		/// <exception cref="System.IndexOutOfRangeException">The index was not in the valid range of indeces for this PriorityQueue.</exception>
		public T ElementAt(int index)
		{
			return itemArray.ElementAt(index);
		}

		/// <summary>
		/// Sets a new value in the queue at specified index.
		/// </summary>
		/// <param name="index">index of the priority queue</param>
		/// <param name="newValue">new value to set</param>
		/// <exception cref="IndexOutOfRangeException"></exception>
		public void SetValue(int index, T newValue)
		{
			try
			{
				itemArray[index] = newValue;
			}
			catch (IndexOutOfRangeException e)
			{
				throw e;
			}
		}

		/// <summary>
		/// Removes the first occurence of a specified item from the PriorityQueue.  The item does not need
		/// to be at the front.
		/// </summary>
		/// <param name="item">The item to be removed.</param>
		/// <returns>true if the item was in the PriorityQueue and was removed;
		/// otherwise, false.</returns>
		public bool Remove(T item)
		{
			return itemArray.Remove(item);			
		}

		/// <summary>
		/// Removes all occurences of a specified item from the PriorityQueue.  The items do not need
		/// to be at the front.
		/// </summary>
		/// <param name="item">The item to be removed from the PriorityQueue.</param>
		/// <returns>The number of items removed from the PriorityQueue.</returns>
		public int RemoveAll(T item)
		{
			int removeCount = 0;
			while(itemArray.Remove(item))
				removeCount++;
			return removeCount;
		}

		/// <summary>
		/// Removes the element at a specified index in the PriorityQueue.
		/// </summary>
		/// <param name="index">Index of the item to be removed.  Zero represents the front of the PriorityQueue.</param>
		/// <exception cref="System.IndexOutOfRangeException">The index was not in the valid range of indeces for this PriorityQueue.</exception>
		public void RemoveAt(int index)
		{
			try
			{
				itemArray.RemoveAt(index);
			}
			catch (IndexOutOfRangeException e)
			{
				throw e;
			}
		}

		/// <summary>
		/// Inserts an element into the PriorityQueue at the specified index.
		/// </summary>
		/// <param name="index">The index where the element is to be inserted.</param>
		/// <param name="item">The item to be inserted.</param>
		/// <exception cref="System.IndexOutOfRangeException">The index was not in the valid range of indeces for this PriorityQueue.</exception>
		public void Insert(int index, T item)
		{
			try
			{
				itemArray.Insert(index, item);
			}
			catch (IndexOutOfRangeException e)
			{
				throw e;
			}
		}

		/// <summary>
		/// Swaps the item at a specified index with the one preceding it.
		/// </summary>
		/// <param name="index">The index whose item is to be swapped with its predecessor.</param>
		/// <exception cref="System.IndexOutOfRangeException">The index must be between <code>1</code> and <code>Count - 1</code> inclusive.</exception>
		public void MoveUp(int index)
		{
			if(index >= Count || index < 1)
				throw new IndexOutOfRangeException("The index must be between 1 and Count - 1 inclusive.");
			T temp = itemArray[index];
			itemArray[index] = itemArray[index - 1];
			itemArray[index - 1] = temp;
		}

		/// <summary>
		/// Swaps the item at a specified index with the one succeeding it.
		/// </summary>
		/// <param name="index">The index whose item is to be swapped with its successor.</param>
		/// <exception cref="System.IndexOutOfRangeException">The index must be between <code>0</code> and <code>Count - 2</code> inclusive.</exception>
		public void MoveDown(int index)
		{
			if (index >= Count - 1 || index < 0)
				throw new IndexOutOfRangeException("The index must be between 0 and Count - 2 inclusive.");
			T temp = itemArray[index];
			itemArray[index] = itemArray[index + 1];
			itemArray[index + 1] = temp;
		}

		/// <summary>
		/// Gets the number of items in the array.
		/// </summary>
		public new int Count
		{
			get { return itemArray.Count; }
		}

		/// <summary>
		/// Gets or sets the capacity of the collection.
		/// </summary>
		public int Capacity
		{
			get { return itemArray.Capacity; }
			set
			{
				itemArray.Capacity = value;
			}
		}

		/// <summary>
		/// Returns an enumerator that iterates through the System.Collections.Generic.List.
		/// </summary>
		/// <returns>The enumerator.</returns>
		public new IEnumerator<T> GetEnumerator()
		{
			return itemArray.GetEnumerator();
		}

		/// <summary>
		/// Returns the index of the first occurence of a specified item in the PriorityQueue.
		/// </summary>
		/// <param name="item">The item to be found in the PriorityQueue.</param>
		/// <returns>The index of the first occurence of the item in the PriorityQueue.</returns>
		public int IndexOf(T item)
		{
			return itemArray.IndexOf((T)item);
		}

		/// <summary>
		/// Returns whether this ICollection has a fixed size.  Returns false for PriorityQueue.
		/// </summary>
		public bool IsFixedSize
		{
			get { return false; }
		}

		/// <summary>
		/// Returns the ReadOnly status of the ICollection.  Returns false for PriorityQueue.
		/// </summary>
		public bool IsReadOnly
		{
			get { return false; }
		}

		/// <summary>
		/// Gets or sets an items value based on a specified index in the PriorityQueue.
		/// </summary>
		/// <param name="index">The index of the item to be set or retrieved.</param>
		/// <returns>The item at the specified index in the PriorityQueue.</returns>
		public T this[int index]
		{
			get
			{
				return itemArray[index];
			}
			set
			{
				itemArray[index] = value;
			}
		}

		/// <summary>
		/// See <see cref="PriorityQueue.Enqueue"/>.
		/// </summary>
		/// <param name="item">The item to be enqueued.</param>
		public void Add(T item)
		{
			this.Enqueue(item);
		}

		/// <summary>
		/// Copies the elements of the PriorityQueue into the specified System.Array, starting
		/// at a particular System.Array index
		/// </summary>
		/// <param name="array">The one-dimensional System.Array that is the destination of
		/// the elements copied from the PriorityQueue.  The System.Array must have zero-based indexing.</param>
		/// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
		/// <exception cref="System.ArgumentNullException">array is null.</exception>
		/// <exception cref="System.ArgumentOutOfRangeException">arrayIndex is less than 0.</exception>
		/// <exception cref="System.ArgumentException">array is multidimensional.-or-The number of elements in the source System.Collections.Generic.ICollection
		/// is greater than the available space from arrayIndex to the end of the destination
		/// array.-or-Type T cannot be cast automatically to the type of the destination array.</exception>
		public new void CopyTo(T[] array, int arrayIndex)
		{
			itemArray.CopyTo(array, arrayIndex);
		}
	}
}
